package 力扣进阶面试题;

import java.util.*;

public class p692前K个高频单词_优先级队列 {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new ArrayList<>();
        if (words == null) return res;

        //1.计算单词表 words 中，每个单词出现的频率
        HashMap<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            } else {
                //当前单词s，已经存在于map中
                int count = map.get(s) + 1;
                map.put(s, count);
            }
        }

        //按单词出现频率由高到低排序
        //2.建小堆, 堆中的每一个元素都是Map的Entry
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {

            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue() == o2.getValue()) {
                    //建堆的时候 当频率相同 按照字母顺序建大堆，字母小的放在后面，因为最后会逆置
                    return o2.getKey().compareTo( o1.getKey() );
                }
                //o1 是我插入的元素，当o1 > o2时，o1直接放到数组的最后
                return o1.getValue() - o2.getValue();//建小堆
            }
        });

        //3.遍历 map中的元素，先将前K个元素，建成小堆
        //再从第 K+1 个元素开始和堆顶元素进行比较。
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            //当 堆中元素个数 小于 K 时，直接往堆中放元素
            if (k > minHeap.size()) {
                minHeap.offer(entry);
            } else {
                //1.当 堆顶元素top和目前遍历到的entry 单词频率相同，按照字母顺序进行构建小堆
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue() == entry.getValue()) {
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    //2. 当 堆顶元素top和目前遍历到的entry 单词频率不相同，将频率大的放入小堆中
                    if (top.getValue() < entry.getValue()) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //现在堆顶是频率最小的单词，再进行调整
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            String key = top.getKey();
            res.add(key);

        }

        Collections.reverse(res);
        return res;
    }
}
